#include <iostream>

using namespace std;

typedef struct _TREE_NODE
{
	int data;
	struct _TREE_NODE* parent;
	struct _TREE_NODE* left_child;
	struct _TREE_NODE* right_child;
}TREE_NODE;

TREE_NODE* create_tree_node(int data)
{
	TREE_NODE* pTreeNode = NULL;
	pTreeNode = (TREE_NODE*)malloc(sizeof(TREE_NODE));

	memset(pTreeNode, 0, sizeof(TREE_NODE));
	pTreeNode->data = data;
	return pTreeNode;
}

TREE_NODE* find_data_in_tree_node(const TREE_NODE* pTreeNode, int data)
{
	if(NULL == pTreeNode)
		return NULL;
	if(data == pTreeNode->data)
		return (TREE_NODE*)pTreeNode;
	else if(data < pTreeNode->data)
		return find_data_in_tree_node(pTreeNode->left_child, data);
	else
		return find_data_in_tree_node(pTreeNode->right_child, data);
}

int count_node_number_in_tree(const TREE_NODE* pTreeNode)
{
	if(NULL == pTreeNode)
		return 0;
	return 1+ count_node_number_in_tree(pTreeNode->left_child)+count_node_number_in_tree(pTreeNode->right_child);
}

int calculate_height_of_tree(const TREE_NODE* pTreeNode)
{
	int left, right;
	if(NULL == pTreeNode)
		return 0;

	left = calculate_height_of_tree(pTreeNode->left_child);
	right = calculate_height_of_tree(pTreeNode->right_child);
	return (left>right)?(left+1):(right+1);
}

STATUS _insert_node_into_tree(TREE_NODE** ppTreeNode, int data, TREE_NODE* pParent)
{
	
	if(NULL == *ppTreeNode){
		*ppTreeNode = (TREE_NODE*)create_tree_node(data);
		(*ppTreeNode)->parent = pParent;
		return TRUE;
	}

	if(data<(*ppTreeNode)->data)
		return _insert_node_into_tree(&(*ppTreeNode)->left_child, data, *ppTreeNode);
	else 
		return _insert_node_into_tree(&(*ppTreeNode)->right_child, data, *ppTreeNode);
}
STATUS insert_node_into_tree(TREE_NODE** ppTreeNode, int data)
{
	if(NULL == ppTreeNode)
		return FALSE;

	if(NULL == *ppTreeNode){
		*ppTreeNode = (TREE_NODE*)malloc(sizeof(TREE_NODE));
		return TRUE;
	}

	return _insert_node_into_tree(ppTreeNode, data, NULL);
}

STATUS delete_node_from_tree(TREE_NODE** ppTreeNode, int data)
{
	if(NULL == ppTreeNode || NULL == *ppTreeNode)
		return FALSE;

	pTreeNode = find_data_in_tree_node(*ppTreeNode, data);
	if(NULL == pTreeNode)
		return FALSE;

	if(*ppTreeNode == pTreeNode){
		if(NULL == pTreeNode->left_child && NULL == pTreeNode->right_child){
			*ppTreeNode = NULL;
		}else if(NULL != pTreeNode->left_child && NULL == pTreeNode->right_child){
			*ppTreeNode = pTreeNode->left_child;
			pTreeNode->left_child->parent = NULL;
		}else if(NULL == pTreeNode->left_child && NULL != pTreeNode->right_child){
			*ppTreeNode = pTreeNode->right_child;  
            pTreeNode->right_child->parent = NULL;  
		}else{
			pLeftMax = find_max_node(pTreeNode->left_child);
			if(pLeftMax == pTreeNode->left_child){
				*ppTreeNode = pTreeNode->left_child;
				(*ppTreeNode)->right_child = pTreeNode->right_child;
				(*ppTreeNode)->right_child->parent = *ppTreeNode;
				(*ppTreeNode)->parent = NULL;
			}else{
				pTreeNode->data = pLeftMax->data;
				pLeftMax->parent->right_child = pLeftMax->left_child;
				pLeftMax->left_child->parent = pLeftMax->parent;
				pTreeNode = pLeftMax; //为了能在后面释放掉这个节点 防止内存泄漏
			}
		}
		free(pTreeNode);
		return TRUE;
	}

	return _delete_node_from_tree(pTreeNode);
}

STATUS  _delete_node_from_tree(TREE_NODE* pTreeNode)
{
	TREE_NODE* pLeftMax;

	if(NULL == pTreeNode->left_child && NULL == pTreeNode->right_child){
		if(pTreeNode== pTreeNode->parent->left_child)
			pTreeNode->parent->left_child = NULL;
		else 
			pTreeNode->parent->right_child = NULL;
	}else if (NULL!= pTreeNode->left_child && NULL == pTreeNode->right_child)
	{
		pTreeNode->left_child->parent = pTreeNode->parent;  
          
        if(pTreeNode == pTreeNode->parent->left_child)  
            pTreeNode->parent->left_child = pTreeNode->left_child;  
        else  
            pTreeNode->parent->right_child = pTreeNode->left_child;  
	}else if(NULL == pTreeNode->left_child && NULL != pTreeNode->right_child){  
        pTreeNode->right_child->parent = pTreeNode->parent;  
          
        if(pTreeNode == pTreeNode->parent->left_child)  
            pTreeNode->parent->left_child = pTreeNode->right_child;  
        else  
            pTreeNode->parent->right_child = pTreeNode->right_child;  
    }else{  
        pLeftMax = find_max_node(pTreeNode->left_child);  
        if(pLeftMax == pTreeNode->left_child){  
              
            if(pTreeNode == pTreeNode->parent->left_child)  
                pTreeNode->parent->left_child = pTreeNode->left_child;  
            else  
                pTreeNode->parent->right_child = pTreeNode->left_child;  
              
            pTreeNode->left_child->parent = pTreeNode->parent;  
            pTreeNode->left_child->right_child = pTreeNode->right_child;  
            pTreeNode->right_child->parent = pTreeNode-> left_child;  
              
        }else{  
            pTreeNode->data = pLeftMax->data;  
            pLeftMax->parent->right_child = pLeftMax->left_child;  
            pLeftMax->left_child->parent = pLeftMax->parent;   
          
            pTreeNode = pLeftMax;  
        }  
    }  
	
	free(pTreeNode);
	return TRUE;
}


int main()
{
    cout << "Hello world!" << endl;
    return 0;
}